/*
* 1.先预处理从1, a, b, c, d, e出发到其他所有点的额单源最短路径
* 2.DFS所有拜访顺序 5! 对于每一种拜访顺序，可以通过查表的方式算出最短距离
*/
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
// #define ONLINE_GUDGE
using namespace std;
using PII = pair<int, int>;
const int N = 50010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int source[6];
int h[N], e[M], w[M], ne[M], idx;
int dist[6][N];
bool st[N];

void AddEdge(int a, int b, int c)
{ e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }

// n*m == 50000*100000 TLE
void spfa(int start, int dist[])
{
    memset(dist, 0x3f, N*4); // 传参数组是spfa的第三个参数的指针，sizeof获取不到dist的大小
    // memset(st, 0, sizeof st);
    dist[start] = 0;

    queue<int> q;
    q.push(start);

    while(q.size())
    {
        int u = q.front(); q.pop();
        st[u] = false;

        for(int i = h[u]; ~i; i=ne[i])
        {
            int v = e[i];
            if(dist[v] > dist[u] + w[i])
            {
                dist[v] = dist[u] + w[i];
                if(!st[v])
                {
                    q.push(v);
                    st[v] = true;
                }
            }
        }

    }
}

void dijkstra(int start, int dist[])
{
    memset(dist, 0x3f, N*4); // 传参数组是spfa的第三个参数的指针，sizeof获取不到dist的大小
    memset(st, 0, sizeof st);
    dist[start] = 0;

    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, start});

    while(q.size())
    {
        int u = q.top().second; q.pop();
        if(st[u]) continue;
        st[u] = 1;

        for(int i = h[u]; ~i; i=ne[i])
        {
            int v = e[i];
            if(dist[v] > dist[u] + w[i])
            {
                dist[v] = dist[u] + w[i];
                q.push({dist[v], v});
                
            }
        }

    }
}

int dfs(int u, int start, int distance)
{
    if(u == 6) return distance;

    int res = INF;
    for(int i = 1; i <= 5; i++)
        if(!st[i])
        {
            int next = source[i];
            st[i] = 1;
            res = min(res, dfs(u+1, i, distance + dist[start][next]));
            st[i] = 0;
        }
    
    return res;
}

int main()
{
    #ifdef ONLINE_JUDGE

    #else
        freopen("./in.txt", "r", stdin);
    #endif

    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;

    source[0] = 1;
    for(int i = 1; i <= 5; i++) cin >> source[i];

    memset(h, -1, sizeof h);
    while(m--)
    {
        int a, b, c; cin >> a >> b >> c;
        AddEdge(a, b, c); AddEdge(b, a, c); 
    }


    for(int i = 0; i <= 5; i++) dijkstra(source[i], dist[i]);

    /*
    for(int i=0;i<6;i++) {
       for(int j = 0; j < 6; j++)
            printf("%d ", dist[i][j]);
        cout << endl; 
    }
    cout << endl;
    */

    memset(st, 0, sizeof st);

    cout << dfs(1, 0, 0);
}